Analyser des algorithmes
Durée estimée: 45 minutes
Questions indécidables et problèmes non-traitables
Nous avons utilisé des algorithmes pour réaliser nos applications et nous avons appris à les mettre en oeuvre pour résoudre certains types de problèmes, comme la recherche ou de tri de données.
Ca peut donner l'impression qu'on peut trouver un algorithme pour résoudre les problèmes, quels qu'il soient. Eh bien non ! Dans cette leçon nous allons examiner des types de problèmes que les algorithmes ne peuvent pas résoudre, ou ne savent pas le faire de façon efficace.
Il y a deux raisons majeures pour lesquelles un problème ne peut pas être résolu :
- Les problèmes indécidables :
Il y a des types de problèmes qu'il est théoriquement impossible de résoudre (quel que soit l'algorithme). -
Les Problèmes Non-traitables ou que l'on ne sait pas résoudre dans la pratique :
Il y a des problèmes impossibles à résoudre dans la pratique -- i.e., il existe des solutions algorithmiques, mais leur efficacité n'est pas suffisante lorsque le nombre de données à traiter augmente.
La vidéo qui suit nous donne une vue d'ensemble des limites algorithmiques de ce type et illustre comment exploiter le caractère concrètement insoluble de ces problèmes pour protéger nos mots de passe et d'autres informations.
(POGIL) Activité de groupe ou pour la classe: Creation d'un mot de apsse robuste (15 minutes)
Pour nous donner une indication de ce qu'il convient de faire pour créer un mot de passe robuste -- i.e., qui résiste aux attaques dites par force brute (qui essaient un grand nombre de possibilités) -- nous allons utiliser un outil de calcul de la résistance ou de la rbustesse d'un mot de passe pour tester la robustesse de quelques exemples.
D'après Wikipedia, un PC de bureau ordinaire disposant d'un logiciel pour casser les mots de passe, peut en essayer 100 millions par seconde.
(NOTE : début 2017, la version française de Wikipediann n'est pas encore suffisamment documentée pour être utilisée).
Le but de cette activité va être d'aboutir à un shéma de définition des mots de passe qu'un PC ordinaire ne pourrait pas cracker en moins de dix ans.
Constituez des équipes ("POGIL") de 4.
Enregistrez les réponses avec cette feuille. (Faites une copie pour avoir une version modifiable/éditable.)
Donnez à chaque membre de l'équipe un des rôles suivants :
| Rôle | Responsabilité |
|---|---|
| Facilitateur | Enregistre les détails du schéma optimal de construction de mots de passe, chosi par l'équipe. |
| Porte-parole | Rend compte du pseudocode des résultats de l'équipe. |
| Contrôleur qualité | Teste l'algorithme avec le gadget ou sans ordinateur. Utilise le calculateur en ligne pour tester les idées de l'équipe dans la création de mots de passe. |
| Analyste process | Valide les résultats de l'équipe et rend compte dans le portfolio des réponses de l'équipe aux questions suivantes. |
Questions
- (Portfolio) Un schéma de mot de passe consiste à imposer au mot de passe une longueur minimale et l'utilisation de différents types de symboles (i.e., lettres, nombres, caractères speciaux). Avec le the Calculateur de robustesse des mots de passe, déterminez le schéma optimal qui permet de résister au moins 10 ans à une attaque de type "force brute" depuis un PC qui essaie 100 millions de mots de passe par seconde.
- (Portfolio) D'après cet article de 2012 , un ordinateur spécialisé dans le cracking des mots de passe peut en essayer 350 milliards par seconde. Comment pourriez vous modifier votre schéma de mot de passe pour continuer à résister 10 ans au attaques de ce type d'ordinateurs ?
- (Portfolio) Cet article a été écrit en 2012. La technologie du cracking s'est améliorée très largement depuis. En faisant l'hypothèse que le nombre de mots de passe testé par seconde, double chaque année, utilisez le calculateur de robustesse de mots de passe, pour déterminer un schéma de mot de passe qui reste valide en 2020 ?
Solutions heuristiques des problèmes Insolubles dans la pratique
Pour une partie des problèmes qui sont Non-traitables (ou impossibles à résoudre concrètement), nous avons qaund même besoin de solutions pratiques. Un exemple de ce type et le Problème du voyageur de commerce: qui doit chosir l'itinéraire optimal (i.e. le plus court), pour passser dans N villes.
C'est une question pour laquelle il existe une réponse, et on aimerait bien l'avoir ! Il y a de nombreuses variantes à cette question, dont la recherche d'itinéraire que l'on fait avec via Michelin, Google maps ou d'autres applications qui nous disent dans quelle direction aller.
Fort Heureusement, si la complexité du problème, ne permet pas d'obtenir rapidement la réponse, il existe ce que l'on appelle des algorithmes heuristiques que les scientifiques utilisent pour résoudre ce type de problèmes. Un algorithme heuristique fournit une solution ou une réponse au problème posé, même si, très souvent, cette solution n'est pas la meilleure possible -- i.e., elle n'est pas optimale.
La vidéo qui suit présente le problème du "voyageur de commerce" ("Traveling Salesman Problem" ou TSP en anglais).
(POGIL) Activité de groupe ou pour la classe : le problème du voyageur de commerce (15 minutes)
Avec les mêmes équipes que ci-dessus, essayons d'évaluer l' heuristique du plus proche voisin pour traiter ce problème.
Vous êtes bibliothécaire à la Gaité Lyrique et devez déposer des livres dans trois bibliothèques de la ville de Paris, rue François Miron, à la bibliothèque Vaclav Havel dans le 18° et à la médiathèque Yourcenar rue d'Alleray dans le 15°, puis repasser à la Gaité lyrique. Il fait beau, vous allez le faire à pied. La carte et le tableau suivants montrent les lieux et les distances qui les séparent.
.
| Distances (km) | Gaité lyrique | F. Miron | V. Havel | M. Yourcenar |
| Gaité lyrique | 0 | 1,8 | 2,8 | 5,6 |
| F. Miron | 1,8 | 0 | 4,5 | 2,3 |
| V. Havel | 2,8 | 4,5 | 0 | 8,2 |
| M. Yourcenar | 5,6 | 5,3 | 8,2 | 0 |
Servez vous de la carte pour répondre aux questions suivantes.
Questions
- En partant et en revenant à la Gaité lyrique, quel itinéraire suivrez ous avec l'heuristique du plus proche voisin, consistant à se diriger vers le lieu le plus proche auquel vous n'êtes pas encore passé ?
- En partant et en revenant à la Gaité lyrique, trouvez l'itinéraire le plus court (qui passe par les trois bibliothèques et revient à la Gaité). (Indice: Pour démontrer que votre itinéraire est optimal, vous devrez le comparer à tous les itinéraires possiblesqui partent et reviennent à Trinity.)
- (Portfolio) Pour les routes qui partent de Trinity et qui y reviennent, fournissez l'itinéraire corresponanat à l'jheuristique du plus proche voisin et l'itinéraire optimal ? Qu'est-ce que celà nous apprend sur l'heursitique du plus proche voisin ?
Auto-contrôle
Pour une chaine de caractères de longueur quelconque qui utilise n'importe quelle combinaison de lettres de 'a' à 'z', écrivez toutes les chaines possibles.
Exemple de question posée à l'examen
En savoir plus ?
Faites de la recherche documentaire en ligne pour identifier les solutions alternatives aux schémas de mots de passe. Par exemple l'authentification à deux facteurs, l'utilisation de données biométriques et le jetons virtuels d'authetification. Quels sont leurs avantages et défauts respectifs ?
Voici un Jeu en ligne qui traite de la question du commis voyageur qui doit trouver la route la plus courte en passant chez tous ss clients.utilise des cartes de l'Vous pouvez vs en servicir pour évluer m'heuristique du plus proche voisin, ou pour mettre au point ou essayer votre propre heuristique pour trouver les itinéraires les plus courts.
Un des domaines des sciences informatiques qui utilise beaucoup l'heuristique, c'est l'Intelligence Artificielle (IA). Vous en avez probablement entendu parler. L'IA s'intéresse particulièrement aux problèmes dans lesquels les humains sont bons, mais dans lesquels les ordinateurs ne sont pas encore assez performants. Par exemple la vision, la parole, lare connaissance vocale, la comporéhension des textes en langage naturel, la planification, la conduite, etc.
Vous aurez remarqué que les avancées dans ces domaines sont rapides -- penssez une seconde à la manière dont fonctionne aujourdplanificationhui Siri et les autres assistants numériques. L'IA est un domaine très vaste. Et, comme pour d'autres sujets, Wikipedia est une bonne mabière pour en apprendre un peu plus, en regardant des termes comme Heuristique ou Intelligence artificielle.
Pour votre Portfolio
Créez une page nommée : Limites des algorithmes dans la catégorie "Réflexions" de votre portfolio, puis répondez aux questions suivantes :- (POGIL) Un schéma de mot de passe consiste à imposer au mot de passe une longueur minimale et l'utilisation de différents types de symboles (i.e., lettres, nombres, caractères speciaux). Avec le the Calculateur de robustesse des mots de passe, déterminez le schéma optimal qui permet de résister au moins 10 ans à une attaque de type "force brute" depuis un PC qui essaie 100 millions de mots de passe par seconde.
- (POGIL) D'après cet article de 2012 , un ordinateur spécialisé dans le cracking des mots de passe peut en essayer 350 milliards par seconde. Comment pourriez vous modifier votre schéma de mot de passe pour continuer à résister 10 ans au attaques de ce type d'ordinateurs ?
- (POGIL) Cet article a été écrit en 2012. La technologie du cracking s'est améliorée très largement depuis. En faisant l'hypothèse que le nombre de mots de passe testé par seconde, double chaque année, utilisez le calculateur de robustesse de mots de passe, pour déterminer un schéma de mot de passe qui reste valide en 2020 ?
- (POGIL) For routes starting and ending at Trinity College, identify the nearest neighbor route and the optimal route. What does this show you about the nearest neighbor heuristic?